The present invention relates to a system of priority control of the execution of programmed tasks in a computer system, wherein the system is a part of the overall operating system. More particularly, this invention relates to a control system for decreasing the overhead time of preferential execution of tasks in a computer system using a queue for scheduling tasks, or a system using tightly coupled multiprocessors.
Priority control of execution of tasks has previously been accomplished by a system which made decisions on the order of execution of tasks by connecting all tasks to a queue and thereafter sequentially searching them one by one. However, this type of well known control system creates an additional problem in that the computer system performance is seriously degraded because of the large resulting overhead time needed for such a sequential queue search.
Japanese Laid-open Patent Application No. 281338/1990 discloses a control system which attempts to solve this problem by improving the system efficiency by checking the length of a task execution queue, and thereafter changing the execution sequence in accordance with the length of the queue. However, this type of control system is not necessarily suitable for priority task execution control, although the search efficiency is improved, because the tasks having the longest queues are executed regardless of the task execution priority. This is because tasks associated with long queues are executed first, regardless of actual task priority when compared to other tasks in the system.
Japanese Laid-open Patent Application No. 24629/1991 discloses another task control system for accelerating task search while attempting to decrease the time overhead required for the addition or deletion of memory associated with "task control blocks." This method of control is accomplished by forming a "task control block" into a double queue consisting of an "arrival-order queue" and a "queue following the execution" priority. However, in that invention consideration of the time required for deleting tasks from a queue is not taken into account. Therefore, to apply such a system to the control of priority task execution, in which a plurality of tasks are present, the frequency of additions or deletions resulting from the double queue increases; and performances are again degraded.
Additionally, some existing computer systems have a problem in that the time for searching a memory space having an executable task is considerably longer than the time required to actually execute the task. Therefore, system performances are again degraded because the number of "memory" spaces increases depending on the scale of the computer system. Also, in computer systems having tightly-coupled multiprocessors, a problem is presented in that the multiprocessor "use efficiency" is decreased. The resulting system performance is not improved proportionally to the number of processors even if a plurality of processors are used. In such cases, the search time is long because the entire system performance is degraded as other processors (which cannot simultaneously execute searches while one processor searches the memory space queue) sit idle until the search is complete.